package leetcode;

import dx.util.RandomUtil;
import org.jetbrains.annotations.Contract;
import org.jetbrains.annotations.NotNull;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * 十大排序算法总结
 * create by duanx 2021/1/3
 *@description： 排序总结
 *@classname: Sort
 *@author: duanx
 *@date: 2021/1/3 16:03
 **/
public class Sort {

    private final static Logger logger = LoggerFactory.getLogger(Sort.class);

    /**
     * 冒泡排序
     * 1.比较相邻的元素，如果第一个比第二个大，就交换他们
     * 2.针对每一个数字做相同的工作，知道结束
     * 3.对每组作比较
     * 4.最佳情况：T(n) = O(n)   最差情况：T(n) = O(n2)   平均情况：T(n) = O(n2)
     * @param array 数组
     */
    public static void bubbleSort(@NotNull int[] array){
        int len = array.length;
        if (len<=1){
            return;
        }
        //外循环控制循环轮次 内循环用来控制每轮比较的次数
        for (int i =0;i<len-1;i++){
            for (int j=0;j<len-1-i;j++){
                if (array[j]>array[j+1]){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     * 先假设最大数为下标第一的位，在遍历数组，将第一与其他比较，
     * 遇到比它大的，将最大数下标改为比他大的那位，一轮比较完成
     * 将最大的数交换致第一位
     * 第二轮比较假设第二位最大，依次循环，直到结束
     * 时间按复杂度：O（n的方）
     * @param array 数组
     */
    public static void selectSort(@NotNull int[] array){
        int len = array.length;
        if (len<=1){
            return;
        }
        for (int i =0;i<len-1;i++){
            int minIndex;
            for (int j=i+1;j<len;j++){
                if(array[j]<array[i]){
                    minIndex = j;
                   int temp = array[minIndex];
                   array[minIndex] = array[i];
                   array[i] = temp;
                }
            }

        }
    }

    /**
     * 插入排序
     * 模仿打扑克时排牌的顺序
     * 1.选定第一个值array[0]作为一个有序数列
     * 2.当前要比较的值从第二个值开始array[i] i=1开始
     * 3.有序数组最大值即array[i-1];
     * 4.将当前值array[i-1]与要比较的值array[i]比较
     * 5.若当前值array[i]<array[i-1],则将要比较的值后移一位 array[i] = array[i-1]
     * 6.将i再减1，若小于0退出比较
     * 7.将i+1此位置即为要插入的位置
     * 8.循环执行到结束
     * @param array 待排序数组
     */
    public static void insertSort(@NotNull int[] array){
        int len = array.length;
        if (len<=1){
            return;
        }
        for (int i=1;i<len;i++){
           int key = array[i];
           int j = i-1;
           while (j>=0&&array[j]>key){
               array[j+1] = array[j];
               j--;
           }
           array[j+1] = key;
        }

    }

    /**
     * 希尔排序（缩小增量排序）
     * 一种增量插入排序
     * @param array 待排序数组
     */
    public static void shellSort(@NotNull int[] array){
        int len = array.length;
        if (len<=1){
            return;
        }
        int gap = len;
        do {
            gap /= 2;
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < array.length; j += gap) {
                    int k = j - gap;
                    while (k >= 0 && array[k] > array[k + gap]) {
                        int temp = array[k];
                        array[k] = array[k + gap];
                        array[k + gap] = temp;
                        k -= gap;
                    }
                }
            }
        } while (gap / 2 != 0);
    }

    /**
     * 归并排序(分治思想)
     * @param array 需要排序的数组
     */
    public static void mergeSort(@NotNull int[] array){
        int len = array.length;
        if (len<=2){
            return;
        }
        int middle = len/2;
        int[] left = Arrays.copyOfRange(array,0,middle);
        int[] right = Arrays.copyOfRange(array,0,middle);
        array = merge(left,right);
    }
    @NotNull
    @Contract(pure = true)
    public static int[] merge(@NotNull int[] left, @NotNull int[] right){
        int[] result = new int[left.length+right.length];
        for (int index=0,i = 0,j=0;index<result.length;index++){
            if (i>=left.length){
                result[index] = right[i+1];
            }else if(j>=right.length){
                result[index] = left[i+1];
            }else if (left[i]>right[j]){
                result[index] = right[j++];
            }else {
                result[index] = left[i++];
            }
        }
        return result;
    }


    public static void main(String[] args) {
//-----------------------------------------------------生成数组---------------------------------------------------------
        long start = System.currentTimeMillis();
        int [] array = RandomUtil.getRandomArray(100000,10,1000888);
        long end = System.currentTimeMillis();
        if (array==null){
            logger.error("生成数组为空，耗时：[{}]ms",end-start);
            throw new RuntimeException("生成数组为空");
        }
        int[] temp = array.clone();
        logger.info("生成数组结束："
//                + Arrays.toString(array)
                +"耗时：[{}]ms",end-start);
//-----------------------------------------------------冒泡排序---------------------------------------------------------
        logger.info("冒泡排序开始："
//                +Arrays.toString(array)
        );
        start = System.currentTimeMillis();
        bubbleSort(array);
        end = System.currentTimeMillis();
        logger.info("冒泡排序结束："
//                +Arrays.toString(array)
                +"，耗时：[{}]ms",end-start);
//-----------------------------------------------------选择排序---------------------------------------------------------
        array =temp.clone();
        logger.info("选择排序开始："
//                +Arrays.toString(array)
        );
        start = System.currentTimeMillis();
        selectSort(array);
        end = System.currentTimeMillis();
        logger.info("选择排序结束"
//                +Arrays.toString(array)
                +"，耗时：[{}]ms",end-start);
//-----------------------------------------------------插入排序---------------------------------------------------------
        array =temp.clone();
        logger.info("插入排序开始："
//                +Arrays.toString(array)
                );
        start = System.currentTimeMillis();
        insertSort(array);
        end = System.currentTimeMillis();
        logger.info("插入排序结束："
//                +Arrays.toString(array)
                +"，耗时：[{}]ms",end-start);
//-----------------------------------------------------希尔排序---------------------------------------------------------
        array =temp.clone();
        logger.info("希尔排序开始："
//                + Arrays.toString(array)
        );
        start = System.currentTimeMillis();
        shellSort(array);
        end = System.currentTimeMillis();
        logger.info("希尔排序结束："
//                +Arrays.toString(array)
                +"，耗时：[{}]ms",end-start);
    }
}
